package com.monkeyboy.dynamic;

/**
 * 题目：
 * 给定两个字符串str1和str2,输出两个字符串的最长公共子串
 * 题目保证str1和str2的最长公共子串存在且唯一。
 * <p>
 * "1AB2345CD","12345EF" --->   "2345"
 * 解题思路：
 * 1.暴力求解，比较消耗内存
 * 2.动态规划
 *
 * @Author Gavin
 * @date 2021.04.21 10:16
 */
public class Str1 {

    public static String solution1(String str1, String str2) {
        int index = 0;
        int maxLength = 0;
        for (int i = 0; i < str2.length(); i++) {
            for (int j = i + 1; j < str2.length(); j++) {
                if (str1.contains(str2.substring(i, j))) {
                    if (maxLength < j - i) {
                        maxLength = j - i;
                        index = i;
                    }
                } else {
                    break;
                }
            }
        }
        if (maxLength == 0) {
            return "-1";
        }
        return str2.substring(index, index + maxLength);
    }

    public static void main(String[] args) {
        System.out.println("123456".substring(1, 2));
    }
}
